package sliding_window

import "sort"

/*
给你两个有序整数数组nums1 和 nums2，请你将 nums2 合并到nums1中，使 nums1 成为一个有序数组。

初始化nums1 和 nums2 的元素数量分别为m 和 n 。你可以假设nums1 的空间大小等于m + n，这样它就有足够的空间保存来自 nums2 的元素。

方法一：直接合并后排序
方法二：双指针：利用数组nums1和nums2已经被排序的性质，可以将两个数组看做队列，每次从两个度列头部取出比较小的数字放到结果中。
方法三：逆向双指针：观察可知，nums1后半部分是空的，可以直接覆盖而不影响结果。
利用m+n-p1-1 >= m-p1-1+n-p2-1
<=> p2>=-1 永远成立，因此p1后面的位置永远足够容纳被插入的元素，不会产生p1的元素被覆盖的情况
*/

func merge1(nums1 []int, m int, nums2 []int, _ int) {
	copy(nums1[m:], nums2)
	sort.Ints(nums1)
}

func merge2(nums1 []int, m int, nums2 []int, n int) {
	sorted := make([]int, 0, m+n)
	p1, p2 := 0, 0
	for {
		if p1 == m {
			sorted = append(sorted, nums2[p2:]...)
			break
		}
		if p2 == n {
			sorted = append(sorted, nums1[p1:]...)
			break
		}
		if nums1[p1] < nums2[p2] {
			sorted = append(sorted, nums1[p1])
			p1++
		} else {
			sorted = append(sorted, nums2[p2])
			p2++
		}

	}

	copy(nums1, sorted)

}

//逆向双指针
func merge3(nums1 []int, m int, nums2 []int, n int) {
	for p1, p2, tail := m-1, n-1, m+n-1; p1 >= 0 || p2 >= 0; tail-- {
		var cur int
		if p1 == -1 { // nums1 到头了
			cur = nums2[p2]
			p2--
		} else if p2 == -1 { // nums2 到头了
			cur = nums1[p1]
			p1--
		} else if nums1[p1] > nums2[p2] { //每次取两者之中的较大者放进 nums 1的最后面。
			cur = nums1[p1]
			p1--
		} else {
			cur = nums2[p2]
			p2--
		}

		//往nums1 后面追加
		nums1[tail] = cur
	}
}
